edu.claflin.finder.algo

Class MatrixPatternAnalyzer

java.lang.Object

edu.claflin.finder.algo.Algorithm

edu.claflin.finder.algo.MatrixPatternAnalyzer

All Implemented Interfaces:

Processable<Graph,Graph>

Deprecated.

No replacement yet. Inefficient and utilizes old algorithm strategy.

public class MatrixPatternAnalyzer
extends Algorithm

Processes a Graph searching for bipartite subgraphs by analyzing the matrices of said Graph.

Version:

3.0.2 February 4, 2016

Author:

Charles Allen Schultz II

Nested Class Summary

Nested classes/interfaces inherited from class edu.claflin.finder.algo.Algorithm

Algorithm.GraphSortOrder

Field Summary

Fields inherited from class edu.claflin.finder.algo.Algorithm

args, counter, listener, PROP_PROGRESS

Constructor Summary

Constructors

Constructor and Description
MatrixPatternAnalyzer() Deprecated. Public constructor for initializing the analyzer.

Method Summary

Modifier and Type	Method and Description
private boolean	checkNodeGroupings(Graph inGraph) Deprecated. Step 2: Iterate on Step 1 through all contiguous node groupings.
private Graph	checkSubGraphs(Graph inGraph, int transpositions) Deprecated. Step 3: Repeat Step 2 for each "Cornered" Sub-matrix of the original Graph.
private boolean	checkZeroMatrices(Graph inGraph, int nodeCap) Deprecated. Step 1: Check for valid 0 Sub-matrices.
java.util.ArrayList<Graph>	process(Graph graph) Deprecated. Processes data.

Methods inherited from class edu.claflin.finder.algo.Algorithm

addPropertyChangeListener, cull, getGraphSortOrder, getPartiteNumber, removePropertyChangeListener, setGraphSortOrder, setPartiteNumber, setProgress

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

MatrixPatternAnalyzer

public MatrixPatternAnalyzer()

Deprecated.

Public constructor for initializing the analyzer. Currently ignores state variables given it doesn't operate on an expansion basis.

Method Detail

process

public java.util.ArrayList<Graph> process(Graph graph)

Deprecated.

Processes data.

Processes the Graph object in four steps.
1) Check for valid 0 Sub-matrices.
2) Iterate on Step 1 through all contiguous node groupings.
3) Repeat Step 2 for each "Cornered" Sub-matrix of the original Graph.
4) Repeat Step 3 for each transposition of the Graph. Each step is carried out in its own method. This method controls Step 4 by looping through all the permutations of the supplied Graph object. The permutation code is based on the "Counting QuickPerm Algorithm" found here:

Parameters:

graph - the Graph object to search for Bipartite subgraphs.

Returns:

the ArrayList of Graph objects containing found bipartite subgraph objects.

checkSubGraphs

private Graph checkSubGraphs(Graph inGraph,
                             int transpositions)

Deprecated.

Step 3: Repeat Step 2 for each "Cornered" Sub-matrix of the original Graph.
A "Cornered" sub-matrix is a sub-matrix whose upper left node lies in the upper left corner of the main matrix. I.e. A(0,0) = B(0,0) if A is the main matrix and B is the sub-matrix.
This method processes Step 2 with each of the n - 1 cornered matrices contained in the original matrix. The smallest cornered matrix containing only one node is not processed (due to it being impossible to sort one node into two disjoint sets.

Parameters:

inGraph -

Returns:

checkNodeGroupings

private boolean checkNodeGroupings(Graph inGraph)

Deprecated.

Step 2: Iterate on Step 1 through all contiguous node groupings. Bipartite graphs may have a ratio of m:n nodes in each disjoint set. Since both node counts are independent of each other, all possible options (except cases where m or n = 0) must be checked.
This section of the algorithm instructs the previous to examine a very specific section of the subgraphs for contiguous zeroes. It iterates through all valid contiguous groupings.

Parameters:

inGraph - the (sub) Graph object to check for bipartiteness.

Returns:

the boolean primitive indicating if the Graph was bipartite.

checkZeroMatrices

private boolean checkZeroMatrices(Graph inGraph,
                                  int nodeCap)

Deprecated.

Step 1: Check for valid 0 Sub-matrices.
Undirected bipartite graphs, when ordered correctly, have two noticeable regions containing no edges, or, if the graph is represented by ones and zeroes, two regions of zeros. The following graph demonstrates this.

 [ 0 0 0 0 1 ]

 [ 0 0 0 1 1 ]

 [ 0 0 0 1 0 ]

 [ 0 1 1 0 0 ]

 [ 1 1 0 0 0 ]

This section of the code verifies that these contiguous regions exist. If they don't, the provided Graph object (or subgraph object in this case) is not Bipartite. This is the core comparison to be performed.

Parameters:

inGraph - the Graph object to check for valid 0 sub-matrices.

nodeCap - the furthest node inward which the upperLeft Matrix should extend to.

Returns:

the boolean primitive indicating if the sub-matrix is bipartite.